Алгоритмическое мышление с помощью Python, часть 2 — Стратегия уменьшения и завоевания

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

Головоломка «Переправа солдат»

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

Как всем солдатам переправиться через реку, оставив двух мальчиков в лодке на том же берегу, с которого они отправились? Определите минимальное количество переходов, которые должна совершить лодка.

(Medium не поддерживает встроенные Python Trinkets, но, пожалуйста, попробуйте решить головоломку, нажав на ссылку, и вернитесь, когда у вас все получится):

Trinket: запускайте код где угодно
Изменить описаниеtrinket.io

Стратегия решения проблем «снижай и властвуй»

Decrease and Conquer – это метод решения вычислительных задач, который берет проблему и сводит ее к более мелкой проблеме, которую легче решить. Иногда его путают с разделяй и властвуй, который похож, но разбивает проблему на несколько более мелких проблем. Для сравнения, Сортировка слиянием и Быстрая сортировка являются примерами алгоритмов "разделяй и властвуй".

Классическими примерами Decrease and Conquer являются:

Бинарный поиск
Алгоритм Евклида
Поиск в глубину
Поиск в ширину
Сортировка вставками и сортировка выбором

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

Существуют различные категории сумм, на которые исходная задача уменьшается в алгоритме «Уменьшить и победить». Однако для всех них справедлив основной принцип:

На каждом шаге алгоритма задача сводится к уменьшенной версии той же задачи до тех пор, пока не будет найдено решение (или не будет обнаружено, что оно невозможно).

Категории уменьшения суммы:

Уменьшение на константу

Часто это константа, равная единице.

Примеры:

Сортировка вставками
Алгоритмы поиска по графу: DFS, BFS

Уменьшение на постоянный коэффициент

Чаще всего в два раза, как в бинарном поиске.

Примеры:

Бинарный поиск
Проблемы с фальшивыми монетами
«Русское крестьянское умножение»

Уменьшение размера переменной

Классическим примером здесь может быть алгоритм Евклида, где величина уменьшения зависит от заданных значений.

Решение головоломки о переправе солдат

А теперь разгадка головоломки о переправе солдат.

Сначала два мальчика должны переправить лодку на другой берег, после чего один из них возвращается с лодкой. Затем один солдат переправляет лодку на другой берег и остается там, пока другой мальчик возвращает лодку. Эти четыре поездки уменьшают размер задачи на 1 (описывается количеством солдат, которым нужно пересечь реку). Таким образом, если эта процедура с четырьмя обходами будет повторена в общей сложности 20 раз, проблема будет решена после 80 обходов. Для общего случая с n солдатами необходимо совершить 4n поездок.

Как ты это сделал? Вы получили такой же результат?

Головоломка "Перевозка солдат" прекрасно иллюстрирует стратегию уменьшения и завоевания для решения вычислительных задач.

Листинг Python для головоломки о переправе солдат

Для справки, вот Python 3 версия головоломки "Переправа солдат".

"""
Ferrying Soldiers Puzzle Python Implementation
Robin Andrews - https://compucademy.net/
"""
import os
import time
NUM_SOLDIERS = 2
def section_break():
    print("*" * 50)
def print_rules():
    pass
def print_state(state, moves_taken):
    os.system("cls" or "clear")
    left_bank, right_bank, bank = state["left_bank"], state["right_bank"], state["bank"]
    print("#### CURRENT STATE OF PUZZLE ####\n")
    print(f"Moves taken: {moves_taken}\n")
    # print(f"{left_bank} | {right_bank}\n")
    print(f"{left_bank['boys']} boys, {left_bank['soldiers']} soldiers | {right_bank['boys']} boys, {right_bank['soldiers']} soldiers\n")
    print(f"Boat is on {bank} bank")
def get_move(state):
    print("\nPuzzle options: \n")
    print("1. Ferry both boys from left to right bank")
    print("2. Ferry both boys from right to left bank")
    print("3. Ferry one boy from left to right bank")
    print("4. Ferry one boy from right to left bank")
    print("5. Ferry a soldier from left to right bank")
    print("6. Ferry a soldier from right to left bank\n")
    choice = 0
    while choice not in [1, 2, 3, 4, 5, 6]:
        try:
            choice = int(input("Choose an action(1-4): "))
        except:
            continue
return choice
def process_move(move, state, moves_taken):
    # We can allow 1 boy, 2 boys or one soldier to cross only
    bank = state["bank"]
    legal_move = False
    # Move both boys from left to right bank
    if move == 1 and bank == "left":
        if state["left_bank"]["boys"] == 2:
            state["left_bank"]["boys"] -= 2
            state["right_bank"]["boys"] += 2
            legal_move = True
            state["bank"] = "right"
    elif move == 2 and bank == "right":
        if state["right_bank"]["boys"] == 2:
            state["right_bank"]["boys"] -= 2
            state["left_bank"]["boys"] += 2
            legal_move = True
            state["bank"] = "left"
    elif move == 3 and bank == "left":
        if state["left_bank"]["boys"] > 0:
            state["left_bank"]["boys"] -= 1
            state["right_bank"]["boys"] += 1
            legal_move = True
            state["bank"] = "right"
    elif move == 4 and bank == "right":
        if state["right_bank"]["boys"] > 0:
            state["right_bank"]["boys"] -= 1
            state["left_bank"]["boys"] += 1
            legal_move = True
            state["bank"] = "left"
    elif move == 5 and bank == "left":
        if state["left_bank"]["soldiers"] > 0:
            state["left_bank"]["soldiers"] -= 1
            state["right_bank"]["soldiers"] += 1
            legal_move = True
            state["bank"] = "right"
    elif move == 6 and bank == "right":
        if state["right_bank"]["soldiers"] > 0:
            state["right_bank"]["soldiers"] -= 1
            state["left_bank"]["soldiers"] += 1
            legal_move = True
            state["bank"] = "left"
if legal_move:
        moves_taken +=1
        return state, moves_taken
    else:
        print("That move is not possible at this time.")
        time.sleep(1)
        return state, moves_taken
def is_win(state):
    return state == {"left_bank": {"boys": 2, "soldiers": 0},
             "right_bank": {"boys": 0, "soldiers": NUM_SOLDIERS},
             "bank": "left"}
def main():
    state = {"left_bank": {"boys": 2, "soldiers": NUM_SOLDIERS},
             "right_bank": {"boys": 0, "soldiers": 0},
             "bank": "left"}
    moves_taken = 0
    while not is_win(state):
        # section_break()
        print_state(state, moves_taken)
        move = get_move(state)
        state, moves_taken = process_move(move, state, moves_taken)  # maybe modify moves_taken in main()
print(f"Well done - you solved the puzzle! You took {moves_taken} moves.")
main()

Удачных вычислений!

Первоначально опубликовано на https://compucademy.net 19 ноября 2020 г.