Войти
ПрограммированиеФорумОбщее

Помогите с поиском кратчайшего пути.

Страницы: 1 2 3 Следующая »
#0
9:36, 16 дек 2009

Доброго времени суток всем!
Помогите с реализацией алгоритма поиска кротчайшего пути.
Дали задние на курсовой. Задание выглядит так: Найти возможные пути для шахматной фигуры слон от одной клетки в другую. Определить кротчайшие.

Как я понял это задание то мне нужно написать программу, с использованием матрицы смежности. Т.е. я представляю шахматную доску так
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.

Вроде через него можно решить эту задачу только вот проблема что-то я не догоняю как его реализовать подскажите кто что знает.
Заранее спасибо за помощь.

#1
11:26, 16 дек 2009

можно еще по пробывать Алгоритм Дейкстры. См. google можно найти уже реализованный.

#2
13:29, 16 дек 2009

Поиск в ширину - BFS

#3
19:47, 16 дек 2009

Зачем такие сложности?
Слон ходит по диагонали. До любой точки доски может дойти за 1 или 2 хода. Нужно ввести новый базис - как раз по диагонали и разложить по нему разность векторов начального и конечного положения. Если одна из составляющих равна 0, то доходим за один ход, иначе - за два. Все. Сложность О(1).

#4
19:54, 16 дек 2009

Да, "Найти возможные пути" - какая-то нечеткая постановка.

#5
20:47, 16 дек 2009

Chipmunk
Угу. Кстати если постановка задачи передана дословно --- то нигде не указывается размерность доски. Слон шахматный --- а доска может быть MxN. :)

#6
21:48, 16 дек 2009

Mekrod
> Найти возможные пути для шахматной фигуры слон от одной клетки в другую. Определить кротчайшие.
Вероятно надо найти все кратчайшие пути.

Вариант решения:
1. Построить граф переходов.
2. Алгоритм Дейкстры, A* и т.п. (поискать например тут )

P.S. Странно, что еще никто не запостил сюда военную атрибутику :)

#7
21:51, 16 дек 2009

>Странно, что еще никто не запостил сюда военную атрибутику :)

Наверно потому, что аффтар раскрыл тему владения гуглом.

#8
21:56, 16 дек 2009

А какой алгоритм проще в реализации?

#9
22:01, 16 дек 2009

Mekrod
> А какой алгоритм проще в реализации?
Да они примерно одинаковые, если не заморачиваться с оптимизацией то там ничего сложного нет.

#10
22:06, 16 дек 2009

Дословно задание звучит так: Найти возможные пути для шахматной фигуры слон от одной клетки до другой в пределах шахматной доски. Определить кротчайшие.

#11
22:20, 16 дек 2009

nbkolchin
> а доска может быть MxN

В первом посте отчетливо указано: NxN.doc.

> Вероятно надо найти все кратчайшие пути.

А их всего 2. Сначала вдоль одной диагонали, а потом вдоль другой, и наоборот.

#12
22:29, 16 дек 2009

andriano
> А их всего 2. Сначала вдоль одной диагонали, а потом вдоль другой, и наоборот.
Рассмотри движение от одной звездочки до другой - три пути(минимум) по 6 шагов. (даже больше получается, точно считать лень :) )

01010101 
*0101010 
01010101 
10101010 
01010101 
10101010 
01010101 
*0101010
#13
23:02, 16 дек 2009

doc.
Ты забываешь, что по условию у нас слон.
В данном случае путь один в два хода.

#14
23:10, 16 дек 2009

andriano
>Ты забываешь, что по условию у нас слон.
Слон может подразумевать просто ограничение на движение.

> В данном случае путь один в два хода.
Вовсе не обязательно. Тут все зависит, что понимается под длиной пути.
Правка: если под длинной подразумеваются ходы то, по идее, задача должна формулироватся в терминах ходов, типа "... за минимальное количество ходов"

Mekrod
Необходимо уточнение задачи.

Страницы: 1 2 3 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.