Научный журнал «Вестник науки»

Режим работы с 09:00 по 23:00

zhurnal@vestnik-nauki.com

Информационное письмо
  1. Главная
  2. Архив
  3. Вестник науки от 9 августа 2026 г.
  4. Научная статья № 43
Просмотры  5 просмотров

СРАВНЕНИЕ ОБУЧАЕМОЙ ЭВРИСТИКИ С КЛАССИЧЕСКИМИ ОЦЕНКАМИ В ЗАДАЧЕ «ПЯТНАШКИ»

Аннотация: в статье проверяется обучаемая эвристика для задачи «Пятнашки». В качестве модели взята линейная регрессия: она получает несколько признаков состояния и возвращает оценку длины решения. Для сравнения оставлены две классические эвристики, Manhattan Distance и Linear Conflict. Эксперимент показывает не только ошибку прогноза, но и работу оценки внутри A*. По числам линейная модель точнее угадывает расстояние до цели, однако в части случаев даёт завышение. Для оптимального поиска это уже не мелкая погрешность, а ограничение метода.

Ключевые слова: машинное обучение, эвристический поиск, алгоритм A*, обучаемая эвристика, головоломка пятнашки, линейная регрессия.

ВВЕДЕНИЕ. В алгоритме A* оценка h(n) нужна для выбора следующего состояния. При слабой оценке поиск быстро разрастается, потому что алгоритм проверяет слишком много похожих вариантов. Если оценка ближе к реальному расстоянию, очередь с приоритетом чаще выбирает полезные состояния.

На практике именно эвристика сильно влияет на скорость A*, хотя формально сам алгоритм не меняется [1]. Manhattan Distance и Linear Conflict удобны тем, что для них понятна логика расчёта. Они не завышают расстояние, значит A* сохраняет оптимальность. Минус тоже понятен: эти оценки видят только часть ограничений на поле.

Поэтому возникает идея посчитать эвристику не вручную, а по данным. Берутся состояния, для них заранее находится оптимальная длина решения, затем модель учится связывать признаки состояния с этой длиной. Похожая постановка встречается в работах по автоматическому построению эвристик [4], [5]. Цель статьи - проверить простую обучаемую оценку на двух уровнях.

Первый уровень: насколько близко она предсказывает длину решения. Второй уровень: что будет, если поставить её в A* вместо обычной эвристики. Отдельно рассматривается допустимость оценки, потому что для кратчайшего пути это не формальность, а условие правильного результата. 1. АНАЛИЗ ТЕОРЕТИЧЕСКИХ ОСНОВ.

Обучаемая эвристика. В работе использована линейная модель. Я выбрала её не из-за максимальной точности, а из-за проверяемости: веса можно посмотреть, обучение занимает мало времени, результат легче объяснить. Для каждого состояния считались Manhattan Distance, Linear Conflict, разность между ними, число фишек не на своих местах, расстояние пустой клетки до цели, ошибки по строкам и столбцам, а также число инверсий.

Правильным ответом считалась оптимальная длина решения, найденная A* с допустимой эвристикой. Модель имеет вид y = w0 + w1*x1 +... + wk*xk. Веса подбирались методом наименьших квадратов. Здесь y означает прогноз длины решения, а x1, x2,..., xk - признаки состояния.

У такой модели нет знания о правилах игры. Она просто подгоняет коэффициенты так, чтобы на обучающих примерах прогноз был ближе к найденной длине пути [3]. У такой оценки сразу появляется слабое место. Регрессия уменьшает среднюю ошибку, а направление ошибки для неё почти безразлично.

Для A* ситуация другая. Недооценка неприятна, потому что поиск становится шире. Завышение опаснее: алгоритм может отложить состояние, через которое проходит кратчайшее решение. Из-за этого в эксперименте считались не только MAE и RMSE, но и доля завышений.

Набор признаков сделан простым. Manhattan Distance даёт грубую нижнюю оценку расстояния. Linear Conflict добавляет случаи, когда фишки мешают друг другу в одной строке или столбце. Число неверно стоящих фишек показывает простое отличие от цели.

Положение пустой клетки тоже учитывается: без пустой клетки не выполняется ни один ход. Число инверсий добавлено как общий признак порядка. Полностью состояние такой набор не описывает, но для учебного эксперимента его достаточно. Можно было бы закодировать всё поле и обучать более сложную модель.

Например, нейронная сеть почти наверняка дала бы другой результат. Но тогда сама эвристика стала бы менее прозрачной. Здесь важнее проверить базовую идею: помогает ли обучение сделать оценку ближе к настоящей длине пути и где после этого ломаются гарантии A*. Таблица 1.

Использованные признаки модели. Отдельно стоит пояснить, почему в таблице нет признака «глубина перемешивания». При генерации состояния она известна, но в реальной задаче такой информации нет. Если добавить её в обучение, модель получит подсказку, которой не будет при обычном решении головоломки.

Поэтому в признаках оставлены только данные, которые можно вычислить по самому полю. Ещё один момент связан с масштабом признаков. Manhattan Distance и Linear Conflict уже похожи на оценку длины решения, а число неверных фишек и положение пустой клетки имеют другой смысл. Линейная модель смешивает эти признаки через веса.

Это удобно, но одновременно рискованно: если обучающая выборка маленькая, отдельные веса могут отражать не общее правило, а особенности выбранных примеров. Именно поэтому такая эвристика проверялась не только как формула прогноза. Её пришлось поставить внутрь A* и посмотреть, что будет с длиной найденного пути. Для алгоритма поиска это важнее, чем красивая ошибка на тестовой выборке. 2.

ПРИКЛАДНАЯ ЧАСТЬ. Методика эксперимента. Эксперимент запускался на Python 3.12.13. Всего было сгенерировано 400 разрешимых состояний: по 80 состояний для глубин перемешивания 10, 15, 20, 25 и 30.

Из них 300 состояний использовались для обучения, ещё 100 оставались для теста. Состояния получались случайными ходами из целевой конфигурации, поэтому они автоматически оставались разрешимыми [7]. Глубина перемешивания не бралась как ответ. Она показывает только число случайных ходов от цели, а кратчайший путь иногда получается короче.

Для каждого состояния сначала отдельно находилась оптимальная длина решения с помощью A*. Уже после этого сравнивались три оценки: Manhattan Distance, Linear Conflict и линейная модель. Для воспроизводимости был задан фиксированный seed. При повторном запуске получается тот же набор состояний.

Это важно для честного сравнения: все методы решают одни и те же конфигурации, а не разные случайные примеры. Для каждого запуска A* записывались время, число раскрытых состояний и длина найденного пути. Время показывает практическую стоимость метода. Число раскрытых состояний отражает, насколько сильно эвристика сужает поиск.

Длина пути нужна как проверка: если путь стал длиннее оптимального, значит оценка уже повлияла на корректность алгоритма. Таблица 2. Ошибка оценки расстояния до цели. Рис. 1.

Средняя абсолютная ошибка оценки. Результаты поиска A*. По ошибке прогноза линейная модель вышла лучше классических оценок. Средняя абсолютная ошибка составила 2,129 хода.

Для Manhattan Distance получилось 3,580, для Linear Conflict - 3,180. Но вместе с этим появилась проблема: в 53,0% тестов модель дала число выше настоящего расстояния. Для обычного прогноза это терпимо, для A* - нет. У классических эвристик ошибка больше по понятной причине: они специально остаются нижними оценками.

Manhattan Distance и Linear Conflict чаще недооценивают расстояние до цели. Поиск из-за этого шире, зато найденный путь остаётся кратчайшим. Линейная модель ближе к реальному расстоянию, но она ошибается в обе стороны. В таблице видно именно этот обмен: прогноз стал точнее, а допустимость пропала.

Таблица 3. Показатели работы A*. Линейная модель раскрыла в среднем 164,18 состояния. Это меньше, чем у Manhattan Distance, и немного меньше, чем у Linear Conflict.

При этом время стало хуже. Причина в накладных расходах: на каждом состоянии заново считаются признаки, потом выполняется расчёт регрессии. На небольших глубинах эта добавка заметна. Таблица 4.

Неоптимальные решения. Рис. 2. Среднее число раскрытых состояний A*.Обсуждение результатов. Из результатов получился не один вывод, а два.

Как модель прогноза линейная регрессия выглядит удачно: ошибка меньше, чем у Manhattan Distance и Linear Conflict. Как эвристика для оптимального A* она уже спорная. Поиск кратчайшего пути требует не просто близкой оценки, а оценки без завышений. По этому условию классические эвристики надёжнее.

Линейную модель не стоит напрямую ставить вместо h(n), если требуется строго оптимальное решение. Более аккуратный вариант - использовать её только как дополнительный критерий сортировки при равных f(n). Основной эвристикой тогда остаётся Manhattan Distance, Linear Conflict или Pattern Database. Данные помогают упорядочить очередь, но гарантия оптимальности остаётся у допустимой оценки [4], [5].

Здесь хорошо видно различие между регрессией и поиском. Для модели обычно радостно, если средняя ошибка на тесте стала меньше. Для A* этого мало: несколько завышенных оценок могут изменить порядок раскрытия состояний. Поэтому такую эвристику надо проверять не только по MAE и RMSE, но и по тому, какие решения реально строит алгоритм.

Сама модель при этом не провалилась. Она действительно дала более близкую оценку длины решения. Ошибка появилась на следующем шаге, когда прогноз стали использовать как эвристику A*. Значит, вопрос не в том, можно ли обучать эвристику.

Вопрос в том, как встроить прогноз в алгоритм, где нужны строгие гарантии. Рис. 3. Доля неоптимальных решений.Проверка корректности эксперимента. Для проверки данные были разделены на обучение и тест.

Состояния из тестовой части не участвовали в подборе весов. Иначе результат был бы слишком оптимистичным: модель могла бы просто подстроиться под уже увиденные примеры. В тесте она работала на новых конфигурациях. Эталонные длины решений вычислялись A* с допустимой эвристикой Manhattan Distance.

Эти значения использовались как база для расчёта ошибки и для проверки оптимальности. Если запуск с линейной моделью находил путь другой длины, случай фиксировался отдельно. Так появился показатель неоптимальных решений. Отдельно считалась доля завышений.

Для Manhattan Distance и Linear Conflict она равна нулю, что совпадает с их допустимостью [1]. У линейной модели завышения есть. Поэтому в статье она рассматривается не как готовая замена классической эвристики, а как экспериментальная оценка. Ограничения работы.

Главное ограничение работы - небольшой размер обучающей выборки. Для демонстрационного эксперимента 300 состояний достаточно, но для устойчивой модели этого мало. Более сложные методы, например нейронные сети, потребуют большего набора примеров и отдельной проверки на независимых данных [3], [6]. Следующий шаг - проверить гибридную схему.

В ней допустимая эвристика отвечает за оптимальность, а обучаемая модель используется только для дополнительного упорядочивания состояний с одинаковым значением f(n). Для A* такой вариант выглядит спокойнее, чем прямая замена эвристики прогнозом модели [4], [5]. Ещё одно направление связано с функцией обучения. Сейчас использован обычный метод наименьших квадратов, а он не запрещает завышения.

Можно попробовать вариант, где завышение штрафуется сильнее, чем недооценка. Средняя ошибка тогда может стать больше, зато оценка будет ближе к требованиям оптимального поиска. Это уже отдельный эксперимент, потому что меняется сама постановка задачи. Практическая интерпретация результатов.

Результаты полезны не только для сравнения времени. По ошибкам линейной модели видно, какие состояния плохо описываются выбранными признаками. Например, если Manhattan Distance и Linear Conflict дают близкие значения, а реальное решение заметно длиннее, значит в состоянии есть ограничения, которые эти признаки почти не отражают. Практический вывод простой: обучаемый компонент нужно встраивать осторожно.

Если требуется кратчайшее решение, модель не должна сама задавать главный приоритет поиска. Если достаточно приближённого ответа, ограничений меньше. В этой работе рассматривается первый случай, поэтому основной акцент сделан на допустимости. ЗАКЛЮЧЕНИЕ.

В работе реализована обучаемая эвристика для задачи «Пятнашки» и проведено сравнение с Manhattan Distance и Linear Conflict. Линейная модель уменьшила среднюю ошибку оценки и раскрыла меньше состояний, чем Manhattan Distance. При этом из-за завышений она дала 5 неоптимальных решений из 100. Для оптимального A* такую модель нельзя использовать без ограничений.

Более подходящий вариант - применять её вместе с допустимой эвристикой.


Полная версия статьи PDF

Номер журнала «Вестник науки» № 8 (101) том 2


Ссылка для цитирования:

Землянская М.М. СРАВНЕНИЕ ОБУЧАЕМОЙ ЭВРИСТИКИ С КЛАССИЧЕСКИМИ ОЦЕНКАМИ В ЗАДАЧЕ «ПЯТНАШКИ» // Журнал «Вестник науки» от 9 августа 2026 г. № 8 (101) том 2. С. 342 - 353. 2026 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/32735 (дата обращения: 12.11.2026 г.)


Альтернативная ссылка латинскими символами: vestnik-nauki.com/article/32735



Нашли грубую ошибку (плагиат, фальсифицированные данные или иные нарушения научно-издательской этики) ?
- напишите письмо в редакцию журнала: zhurnal@vestnik-nauki.com


Вестник науки © 2026.    16+




* В выпусках журнала могут упоминаться организации (Meta, Facebook, Instagram) в отношении которых судом принято вступившее в законную силу решение о ликвидации или запрете деятельности по основаниям, предусмотренным Федеральным законом от 25 июля 2002 года № 114-ФЗ «О противодействии экстремистской деятельности» (далее - Федеральный закон «О противодействии экстремистской деятельности»), или об организации, включенной в опубликованный единый федеральный список организаций, в том числе иностранных и международных организаций, признанных в соответствии с законодательством Российской Федерации террористическими, без указания на то, что соответствующее общественное объединение или иная организация ликвидированы или их деятельность запрещена.