Птички

1. Курсовая работа

Выполнили: Андреев, Доброгорская, Саблин,
Селезнёв

2. Содержание

Введение
3
Особенности метода
5
Алгоритм
8
Достоинства
9
Недостатки
10

3. Введение

3
Введение
Задача о птицах
Оптимально разделить
всех птиц по типам так,
чтобы каждая
колонка содержала только
один вид птиц и была либо
полностью заполнена
птицами одного типа, либо
пуста

4. Метод решения

5. A* (A-star) с эвристикой

5
A* (A-star) с эвристикой
Задача формулируется как поиск пути в пространстве состояний,
где:
1. Состояние — текущее расположение птиц по колонкам
2. Переход — перемещение крайней птицы из одной колонки в
другую
3. Целевое состояние — все колонки либо пусты, либо полностью
заполнены птицами одного типа

6. Основные компоненты A*

6
Основные компоненты A*
Представление данных: Колонки представляются как
кортежи строк (для хеширования)
• Доска (board) — кортеж колонок
• Ход: (src_index, dst_index, bird_type)
a) Функция стоимости g(n):
• Простое количество сделанных ходов
• Каждый ход имеет стоимость 1

7.

b) Эвристическая функция h(n):
• Оценивает "качество" текущего состояния
• Штраф +10 за каждую пару соседних птиц разного типа в
одной колонке
• Бонус -2 × длина для полностью однородных колонок
• Чем меньше значение, тем ближе состояние к целевому
c) Приоритетная очередь:
• Используется heapq для эффективного извлечения состояния
с минимальной оценкой
• Приоритет = g(n) + h(n)

8. Алгоритм поиска

8
Алгоритм поиска
1. Инициализировать очередь с начальным состоянием
2. Инициализировать множество посещенных состояний
3. Пока очередь не пуста:
a. Извлечь состояние с наименьшим приоритетом
b. Если это целевое состояние → вернуть путь
c. Сгенерировать все возможные ходы из текущего состояния
d. Для каждого хода:
- Применить ход, получить новое состояние
- Если состояние не посещалось:
* Добавить в посещенные
* Вычислить новый путь (g+1)
* Вычислить эвристику h для нового состояния
* Добавить в очередь с приоритетом (g+1+h)

9. Достоинства

9
Достоинства
Полнота: A* с корректной эвристикой находит решение,
если оно существует
Оптимальность: С эвристикой, не переоценивающей
реальную стоимость, A* находит оптимальное решение
Эффективность: Эвристика направляет поиск в
перспективном направлении
Универсальность: Работает для любого количества
колонок и типов птиц

10. Недостатки

10
Недостатки
Пространство состояний:
Экспоненциальное от
количества птиц
Время работы: Зависит от
качества эвристики и
количества свободных
колонок
Память: Хранение всех
посещенных состояний
может требовать много
памяти

11. Спасибо за внимание!