Тёмная тема
Парни а что если всю шахматную доску представить как систему координат Х Y
тогда можно поиск сделать всего на восьми условиях. В зависимости от места расположения фигуры.
doc.
> Найти возможные пути для шахматной фигуры слон от одной клетки до другой в
> пределах шахматной доски. Определить кротчайшие.
Все до слова написал как в задании указанно.
Почитал по А* там будет проблема в реализации она считает только по вертикали и горизонтали цену пути, а значит по диагонали считать не будет и алгоритм запнется на первом шаге.
Mekrod
> Почитал по А* там будет проблема в реализации она считает только по вертикали и горизонтали цену пути, а значит по диагонали считать
> не будет и алгоритм запнется на первом шаге.
Не запнется. Оценочная функция это т.с. рекомендация, не более. Можно вобще её сделать константой, единственно на что она влияет - на скорость поиска.
Правка: Т.к. тебе надо находить совокупность путей, наверное, лучше использовать волновой алгоритм - там при достижении целевой точки будут достигать одновременно все пути за данное число шагов, потом останется их только рекурсивно пробежать и занести в списочек.
doc.
> Не запнется. Оценочная функция это т.с. рекомендация, не более. Можно вобще её
> сделать константой, единственно на что она влияет - на скорость поиска.
Тогда подскажи как это сделать, если можешь приведи пример. Заранее спасибо.
Какая нафиг Дейкстра или A*! Тут все ребра единичного веса поэтому самый простой и быстрый алгоритм это БФС (конечно понимаю, что это частный случай Дейкстры, но все равно нечего путать народ)
Mekrod
> Тогда подскажи как это сделать,
Все можно найти в Гугле, загляни, например на Wiki.
id-mikle
> Тут все ребра единичного веса поэтому самый простой и быстрый алгоритм это БФС
Ну, самый простой это вобще итерационный волновик, ни списков, ни графов - простенький массивчик и цикл с проверкой.
Правка: учитывая, размеры массива 4x8 возможно, что окажется и самым быстрым вариантом из-за простоты реализации.
doc.
итерационный волновик и есть БФС.
Mekrod
> Все до слова написал как в задании указанно.
кротчайшие - это именно так и указано?
Первый пост достаточно длинный и, кроме того, внутренне противоречивый. Чтобы восстановить условие задачи, ты отдели то, как было сформулировано задание от своих собственных измышлений, как его надо делать.
andriano
> кротчайшие - это именно так и указано?
Сорри за ошибку там написано кратчайшие.
Найти возможные пути для шахматной фигуры слон от одной клетки до другой в пределах шахматной доски. Определить кратчайшие.
andriano
Я понимаю простоту и гениальность. Но доска наверно может быть и не пустой. там всякие пешки и так далее.
Найти возможные пути для шахматной фигурых
Их может быть бесконечно. Слон по кругу бегать тоже может.
а вообще не понял сути проблемы. Автор вроде и задачу понял, и алгоритмы нашел. Что еще ему нужно??
id-mikle
> Тут все ребра единичного веса поэтому самый простой и быстрый алгоритм это БФС
Как так, ведь BFS по сути обрубленная Дийкстра.
Mekrod
> Найти возможные пути для шахматной фигуры слон от одной клетки до другой в
> пределах шахматной доски. Определить кратчайшие.
В данной постановке ВСЕ пути найти принципиально невозможно, т.к. их бесконечное количество, а кратчайший путь - один или два хода. В последнем случае возможно наличие двух кратчайших путей.
Примечание: задача не имеет решений, если исходная и целевая клетки имеют различный цвет. Это тоже надо предусмотреть в решении.
Тема в архиве.