Тёмная тема
- nbkolchin
- Постоялец
Доброго времени суток всем!
Помогите с реализацией алгоритма поиска кротчайшего пути.
Дали задние на курсовой. Задание выглядит так: Найти возможные пути для шахматной фигуры слон от одной клетки в другую. Определить кротчайшие.
Как я понял это задание то мне нужно написать программу, с использованием матрицы смежности. Т.е. я представляю шахматную доску так
01010101
10101010
01010101
10101010
01010101
10101010
01010101
10101010
где 1 отмечается вершины между которыми есть дуги.
Дальше вводятся начальная точка и конечная точка.
И начинается обход всех вершин и поиска путей от начальной точки до конечной, потом выбрав кротчайший и вывести результат.
Читал про алгоритм Флойда-Уоршелла
Алгоритм Флойда-Уоршола
Авторы алгоритма: Роберт Флойд (Robert Floyd) и Стивен Уоршол (Stephen Warshall), которые (независимо друг от друга?) разработали его в 1962 году.
С помощью алгоритма Флойда-Уоршола можно найти кратчайшие пути между всему парами вершин за O (N3), где N - количество вершин в графе.
На вход подаётся любой граф (ориентированный или неориентированный), заданный своей матрицей смежности. На выходе будет матрица D[1..N][1..N], в каждом элементе D[J] которой будет длина кратчайшего пути между вершинами I и J.
Алгоритм.
Изначально присвоим матрице D матрицу смежности графа (однако, если две вершины не связаны ребром, то соответствующие значения в матрице сделаем равными бесконечности). Теперь будет перебирать все K от 1 до N, а затем для каждого K перебирать всевозможные пары вершин (I, J) и пытаться уменьшить длину пути между вершинами I и J с помощью вершины K (т.е. будем брать путь из I в K и из K в J и пытаться этим путём улучшить путь между I и J). По окончании этого процесса мы получим искомую матрицу D.
Вроде через него можно решить эту задачу только вот проблема что-то я не догоняю как его реализовать подскажите кто что знает.
Заранее спасибо за помощь.
можно еще по пробывать Алгоритм Дейкстры. См. google можно найти уже реализованный.
Поиск в ширину - BFS
Зачем такие сложности?
Слон ходит по диагонали. До любой точки доски может дойти за 1 или 2 хода. Нужно ввести новый базис - как раз по диагонали и разложить по нему разность векторов начального и конечного положения. Если одна из составляющих равна 0, то доходим за один ход, иначе - за два. Все. Сложность О(1).
Да, "Найти возможные пути" - какая-то нечеткая постановка.
Chipmunk
Угу. Кстати если постановка задачи передана дословно --- то нигде не указывается размерность доски. Слон шахматный --- а доска может быть MxN. :)
Mekrod
> Найти возможные пути для шахматной фигуры слон от одной клетки в другую. Определить кротчайшие.
Вероятно надо найти все кратчайшие пути.
Вариант решения:
1. Построить граф переходов.
2. Алгоритм Дейкстры, A* и т.п. (поискать например тут )
P.S. Странно, что еще никто не запостил сюда военную атрибутику :)
>Странно, что еще никто не запостил сюда военную атрибутику :)
Наверно потому, что аффтар раскрыл тему владения гуглом.
А какой алгоритм проще в реализации?
Mekrod
> А какой алгоритм проще в реализации?
Да они примерно одинаковые, если не заморачиваться с оптимизацией то там ничего сложного нет.
Дословно задание звучит так: Найти возможные пути для шахматной фигуры слон от одной клетки до другой в пределах шахматной доски. Определить кротчайшие.
nbkolchin
> а доска может быть MxN
В первом посте отчетливо указано: NxN.doc.
> Вероятно надо найти все кратчайшие пути.
А их всего 2. Сначала вдоль одной диагонали, а потом вдоль другой, и наоборот.
andriano
> А их всего 2. Сначала вдоль одной диагонали, а потом вдоль другой, и наоборот.
Рассмотри движение от одной звездочки до другой - три пути(минимум) по 6 шагов. (даже больше получается, точно считать лень :) )
01010101 *0101010 01010101 10101010 01010101 10101010 01010101 *0101010
doc.
Ты забываешь, что по условию у нас слон.
В данном случае путь один в два хода.
andriano
>Ты забываешь, что по условию у нас слон.
Слон может подразумевать просто ограничение на движение.
> В данном случае путь один в два хода.
Вовсе не обязательно. Тут все зависит, что понимается под длиной пути.
Правка: если под длинной подразумеваются ходы то, по идее, задача должна формулироватся в терминах ходов, типа "... за минимальное количество ходов"
Mekrod
Необходимо уточнение задачи.
Тема в архиве.