Алгоритм всегда ведёт себя по разному, изза того что сид рандома прикован в системному времени, на полных графах находит наилучшее решение в среднем за 10-15 итераций, однако если же граф не полный, что очень плохо для данного алгоритма, то 75 итераций (75 это константа установленная в моей реализации) не всегда хватает для нахождения хоть какого то пути, для этого существуют усовершенствованные алгоритмы муравьёв, в данной статье я разобрал классический муравьиный алгоритм.
Согласен, но смотря как этот лабиринт был сгенерирован, если алгоритмом Эллера, где единственный путь между двумя точками, то DFS тут тоже подходит. Оба подходят, но BFS лучше, согласен, но еще лучше Волновой Алгоритм для этого подходит, хотя принцип действия почти как у BFS
Алгоритм там не сложный, сложнее его понять и реализовать, как раз для этого придется прочитать не мало тех.материала, согласен, но в одну статью это уместить можно, убрав воду. Причем в таких книгах больше половины (как по мне) просто дискуссия и обсуждения, доказательства, теоремы и т.п.
Например, задача коммивояжера, эта та задача и алгоритм ее решения точно тема отдельной статьи. А BFS DFS это база, да и кратчайшие пути межд вершинами и всеми парами вершин, как по мне база. Согласен, что и целой книги не хватит для описания алгоритмов на графах.
Так там же есть заголовок перед этим, "Представление графа в коде", потому что без этого было бы непонятно такое выражение graph(v1, v2), а до этого есть заголовок, про сам граф, где я отставил ссылки для ознакомления с самим понятием графа.
Матрица смежности это один из вариантов представления графа в памяти компьютера. Есть и другие способы, но простой обёртки, которая знает количество рёбер, вершин и тип графа, достаточно для большинства задач, можешь ознакомиться с этой обёрткой у меня на github'e "GraphAlgorithms"
Да, клеточный автомат не решит, в Хабре также есть статья про генерацию пещер, там решается эта проблема, ссылочку, к сожалению, не помню. Но гуглится не особо сложно
1) Оптимизацию по поводу сливания в более выгодную сторону я не делал у себя в коде, так как это не влияет, в любом случае надо перебирать всю строку, и присваивание копированием примитивных типов работает за константное время
2) Вероятности ставить стену и не ставить стену равны, если например сделать вероятность ставить стенки равной 1, то структура лабиринта будет примерно такой:
Каждая строка, кроме последней, будет иметь всё вертикальные стенки и ни одной горизонтальной, а последняя строка будет иметь всё горизонтальные стенки и ни одной вертикальной
Если же наоборот, вероятность ставить стену 0, то ситуация поворачивается в обратную сторону, первая строка не будет иметь ни вертикальных стенок ни горизонтальных, остальные строки будут иметь все вертикальные стенки
3) Не понял сути вопроса про однородность лабиринта.
Плюс в статье, которые вы скинули, нет толкового разбора пошагово на определённых псевдослучайных числах, и поэтому понимание реализации алгоритма на бумаге ухудшается.
Также в той статье не написано как правильно объединять множества, потому что многие считают, что сама по себе ячейка в строке является множеством, но нет, она лишь принадлежит определённому множеству
Мне пожаловались о том, что как раз таки статья которую вы прикрепили, не раскрывает полностью суть данного алгоритма, и лабиринт получается не идеальным.
Алгоритм всегда ведёт себя по разному, изза того что сид рандома прикован в системному времени, на полных графах находит наилучшее решение в среднем за 10-15 итераций, однако если же граф не полный, что очень плохо для данного алгоритма, то 75 итераций (75 это константа установленная в моей реализации) не всегда хватает для нахождения хоть какого то пути, для этого существуют усовершенствованные алгоритмы муравьёв, в данной статье я разобрал классический муравьиный алгоритм.
согласен с вами, я как раз над этим сейчас работаю
Согласен, но смотря как этот лабиринт был сгенерирован, если алгоритмом Эллера, где единственный путь между двумя точками, то DFS тут тоже подходит. Оба подходят, но BFS лучше, согласен, но еще лучше Волновой Алгоритм для этого подходит, хотя принцип действия почти как у BFS
Алгоритм там не сложный, сложнее его понять и реализовать, как раз для этого придется прочитать не мало тех.материала, согласен, но в одну статью это уместить можно, убрав воду. Причем в таких книгах больше половины (как по мне) просто дискуссия и обсуждения, доказательства, теоремы и т.п.
Согласен, добавлю
Ничего не было перепутано, просто заголовки читать надо, заголовок, перед упоминанием обертки матрицы смежности, такой "Представление графа в коде"
Например, задача коммивояжера, эта та задача и алгоритм ее решения точно тема отдельной статьи. А BFS DFS это база, да и кратчайшие пути межд вершинами и всеми парами вершин, как по мне база. Согласен, что и целой книги не хватит для описания алгоритмов на графах.
Так там же есть заголовок перед этим, "Представление графа в коде", потому что без этого было бы непонятно такое выражение graph(v1, v2), а до этого есть заголовок, про сам граф, где я отставил ссылки для ознакомления с самим понятием графа.
Согласен, но важно знать не только наличие этих библиотек, но и как эти алгоритмы работают
Матрица смежности это один из вариантов представления графа в памяти компьютера. Есть и другие способы, но простой обёртки, которая знает количество рёбер, вершин и тип графа, достаточно для большинства задач, можешь ознакомиться с этой обёрткой у меня на github'e "GraphAlgorithms"
Да, клеточный автомат не решит, в Хабре также есть статья про генерацию пещер, там решается эта проблема, ссылочку, к сожалению, не помню. Но гуглится не особо сложно
чем больше путей от одной точки до другой тем легче сам лабиринт, данный алгоритм гарантирует что будет единственный путь между любыми точками.
Как нибудь я протестирую это и напишу в комментарии или добавлю в статью заголовок со средней длиной пути по от одного угла до другого угла
У каждого алгоритма, по моему мнению, есть свои минусы(
В этом и суть псевдослучайных чисел, они не случайные, эти числа получаются путем математических алгоритмов, поэтому и такой результат
согласен, но такого эксперимента я к сожалению не проводил)
Всё зависит от бога рандома, поэтому каждый лабиринт и является уникальным
1) Оптимизацию по поводу сливания в более выгодную сторону я не делал у себя в коде, так как это не влияет, в любом случае надо перебирать всю строку, и присваивание копированием примитивных типов работает за константное время
2) Вероятности ставить стену и не ставить стену равны, если например сделать вероятность ставить стенки равной 1, то структура лабиринта будет примерно такой:
Каждая строка, кроме последней, будет иметь всё вертикальные стенки и ни одной горизонтальной, а последняя строка будет иметь всё горизонтальные стенки и ни одной вертикальной
Если же наоборот, вероятность ставить стену 0, то ситуация поворачивается в обратную сторону, первая строка не будет иметь ни вертикальных стенок ни горизонтальных, остальные строки будут иметь все вертикальные стенки
3) Не понял сути вопроса про однородность лабиринта.
Плюс в статье, которые вы скинули, нет толкового разбора пошагово на определённых псевдослучайных числах, и поэтому понимание реализации алгоритма на бумаге ухудшается.
Также в той статье не написано как правильно объединять множества, потому что многие считают, что сама по себе ячейка в строке является множеством, но нет, она лишь принадлежит определённому множеству
Мне пожаловались о том, что как раз таки статья которую вы прикрепили, не раскрывает полностью суть данного алгоритма, и лабиринт получается не идеальным.
поменял