Сообщение Re: Implicit graphs от 12.11.2020 13:15
Изменено 12.11.2020 13:16 Qbit86
Re: Implicit graphs
Здравствуйте, kaa.python, Вы писали:
KP>обычно алгоритмы поиска в графе предполагают что весь граф доступен в рамках одного адресного пространства...
Не обязательно. Можно рассмотреть и неявные графы, которые вообще в памяти никак не представлены, а генерируются по ходу работы алгоритма.
Много алгоритмов требуют от графа всего две функции:
• по дуге получить голову (это «половина» функции инцидентности графа),
• по вершине получить последовательность исходящих дуг.
Эта последовательность исходящих дуг, как и набор вершин, не обязаны в явном виде находится где-то в памяти, и вообще быть ограниченными.
Представь себе граф, заданный ходами коня на шахматной доске. Какая модель этого графа? Понятно, ты не будешь «хранить» клетки этой доски, или ссылки между ними. Вся твоя модель — это просто размер доски (в том числе бесконечный).
Или более общий граф, представляющий собой дерево позиций настольной игры. Вершины — позиции, дуги — ходы. Обходы этого графа вполне успешно работают в алгоритмах AI типа альфа-бета-отсечения; хотя, очевидно, полный граф шахмат или го ни в какую память не влезет.
KP>обычно алгоритмы поиска в графе предполагают что весь граф доступен в рамках одного адресного пространства...
Не обязательно. Можно рассмотреть и неявные графы, которые вообще в памяти никак не представлены, а генерируются по ходу работы алгоритма.
Много алгоритмов требуют от графа всего две функции:
• по дуге получить голову (это «половина» функции инцидентности графа),
• по вершине получить последовательность исходящих дуг.
Эта последовательность исходящих дуг, как и набор вершин, не обязаны в явном виде находится где-то в памяти, и вообще быть ограниченными.
Представь себе граф, заданный ходами коня на шахматной доске. Какая модель этого графа? Понятно, ты не будешь «хранить» клетки этой доски, или ссылки между ними. Вся твоя модель — это просто размер доски (в том числе бесконечный).
Или более общий граф, представляющий собой дерево позиций настольной игры. Вершины — позиции, дуги — ходы. Обходы этого графа вполне успешно работают в алгоритмах AI типа альфа-бета-отсечения; хотя, очевидно, полный граф шахмат или го ни в какую память не влезет.
Re: Implicit graphs
Здравствуйте, kaa.python, Вы писали:
KP>обычно алгоритмы поиска в графе предполагают что весь граф доступен в рамках одного адресного пространства...
Не обязательно. Можно рассмотреть и неявные графы, которые вообще в памяти никак не представлены, а генерируются по ходу работы алгоритма.
Много алгоритмов требуют от графа всего две функции:
• по дуге получить голову (это «половина» функции инцидентности графа),
• по вершине получить последовательность исходящих дуг.
Эта последовательность исходящих дуг, как и набор вершин, не обязаны в явном виде находиться где-то в памяти, и вообще быть ограниченными.
Представь себе граф, заданный ходами коня на шахматной доске. Какая модель этого графа? Понятно, ты не будешь «хранить» клетки этой доски, или ссылки между ними. Вся твоя модель — это просто размер доски (в том числе бесконечный).
Или более общий граф, представляющий собой дерево позиций настольной игры. Вершины — позиции, дуги — ходы. Обходы этого графа вполне успешно работают в алгоритмах AI типа альфа-бета-отсечения; хотя, очевидно, полный граф шахмат или го ни в какую память не влезет.
KP>обычно алгоритмы поиска в графе предполагают что весь граф доступен в рамках одного адресного пространства...
Не обязательно. Можно рассмотреть и неявные графы, которые вообще в памяти никак не представлены, а генерируются по ходу работы алгоритма.
Много алгоритмов требуют от графа всего две функции:
• по дуге получить голову (это «половина» функции инцидентности графа),
• по вершине получить последовательность исходящих дуг.
Эта последовательность исходящих дуг, как и набор вершин, не обязаны в явном виде находиться где-то в памяти, и вообще быть ограниченными.
Представь себе граф, заданный ходами коня на шахматной доске. Какая модель этого графа? Понятно, ты не будешь «хранить» клетки этой доски, или ссылки между ними. Вся твоя модель — это просто размер доски (в том числе бесконечный).
Или более общий граф, представляющий собой дерево позиций настольной игры. Вершины — позиции, дуги — ходы. Обходы этого графа вполне успешно работают в алгоритмах AI типа альфа-бета-отсечения; хотя, очевидно, полный граф шахмат или го ни в какую память не влезет.