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

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

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

Парни а что если всю шахматную доску представить как систему координат Х Y
тогда можно поиск сделать всего на восьми условиях. В зависимости от места расположения фигуры.

#16
23:38, 16 дек 2009

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

#17
23:40, 16 дек 2009

Почитал по А* там будет проблема в реализации она считает только по вертикали и горизонтали цену пути, а значит по диагонали считать не будет и алгоритм запнется на первом шаге.

#18
23:59, 16 дек 2009

Mekrod
> Почитал по А* там будет проблема в реализации она считает только по вертикали и горизонтали цену пути, а значит по диагонали считать
> не будет и алгоритм запнется на первом шаге.
Не запнется. Оценочная функция это т.с. рекомендация, не более. Можно вобще её сделать константой, единственно на что она влияет - на скорость поиска.

Правка: Т.к. тебе надо находить совокупность путей, наверное, лучше использовать волновой алгоритм - там при достижении целевой точки будут достигать одновременно все пути за данное число шагов, потом останется их только рекурсивно пробежать и занести в списочек.

#19
0:07, 17 дек 2009

doc.
> Не запнется. Оценочная функция это т.с. рекомендация, не более. Можно вобще её
> сделать константой, единственно на что она влияет - на скорость поиска.
Тогда подскажи как это сделать, если можешь приведи пример. Заранее спасибо.

#20
0:15, 17 дек 2009

Какая нафиг Дейкстра или A*! Тут все ребра единичного веса поэтому самый простой и быстрый алгоритм это БФС (конечно понимаю, что это частный случай Дейкстры, но все равно нечего путать народ)

#21
0:22, 17 дек 2009

Mekrod
> Тогда подскажи как это сделать,
Все можно найти в Гугле, загляни, например на Wiki.

id-mikle
> Тут все ребра единичного веса поэтому самый простой и быстрый алгоритм это БФС
Ну, самый простой это вобще итерационный волновик, ни списков, ни графов - простенький массивчик и цикл с проверкой.
Правка: учитывая, размеры массива 4x8 возможно, что окажется и самым быстрым вариантом из-за простоты реализации.

#22
1:08, 17 дек 2009

doc.
итерационный волновик и есть БФС.

#23
20:34, 17 дек 2009

Mekrod
> Все до слова написал как в задании указанно.

кротчайшие - это именно так и указано?

Первый пост достаточно длинный и, кроме того, внутренне противоречивый. Чтобы восстановить условие задачи, ты отдели то, как было сформулировано задание от своих собственных измышлений, как его надо делать.

#24
7:42, 18 дек 2009

andriano
> кротчайшие - это именно так и указано?
Сорри за ошибку там написано кратчайшие.

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

#25
10:55, 18 дек 2009

andriano

Я понимаю простоту и гениальность. Но доска наверно может быть и не пустой. там всякие пешки и так далее.

#26
10:56, 18 дек 2009

Найти возможные пути для шахматной фигурых

Их может быть бесконечно. Слон по кругу бегать тоже может.

#27
10:57, 18 дек 2009

а вообще не понял сути проблемы.  Автор вроде и задачу понял, и алгоритмы нашел. Что еще ему нужно??

#28
12:50, 18 дек 2009

id-mikle
> Тут все ребра единичного веса поэтому самый простой и быстрый алгоритм это БФС
Как так, ведь BFS по сути обрубленная Дийкстра.

#29
21:35, 18 дек 2009

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

В данной постановке ВСЕ пути найти принципиально невозможно, т.к. их бесконечное количество, а кратчайший путь - один или два хода. В последнем случае возможно наличие двух кратчайших путей.

Примечание: задача не имеет решений, если исходная и целевая клетки имеют различный цвет. Это тоже надо предусмотреть в решении.

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

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