Построение цикла опорного плана транспортной задачи

Рейтинг: 2Ответов: 1Опубликовано: 04.04.2023

Решить задачу на Python.

Дана матрица опорного плана транспортной задачи (частный случай задач оптимизации) в виде двумерного массива (количество столбцов для каждой строки постоянно и неизменно):

matrix = [
    [50, 0, 0, 0, 0],
    [0, 60, 0, 0, 40],
    [50, 10, 50, 40, 0]
]

Требуется написать функцию find_cycle, принимающую в качестве аргументов:

  • позицию (строка, столбец) нулевой клетки, с которой надо построить цикл
  • матрицу, в которой нужно построить цикл;

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

Запрещено использовать любые библиотеки, в т.ч. встроенные (NumPy, SciPy, Pandas и т.д.)

Правила нахождения цикла в матрице:

  1. Цикл всегда строится от нулевой клетки;
  2. Для любой матрицы цикл всегда существует, при этом он единственен для конкретной нулевой клетки (других циклов для данной нулевой клетки построить нельзя);
  3. Цикл начинается и заканчивается в одной и той же нулевой клетке;
  4. Цикл поворачивает только в заполненных базисных клетках матрицы опорного плана (те клетки, где есть числа);
  5. Цикл всегда поворачивает под углом 90 градусов (вершина1 в строке → вершина1 в столбце → вершина2 в строке → и т.д.);
  6. Цикл может "перепрыгивать" любое количество базисных клеток, если это необходимо;
  7. Цикл может иметь различную форму (прямоугольник, квадрат, несколько прямоугольников и т.д.)

Примеры работы функции (для матрицы из примера выше):

>>> find_cycle((0, 1), matrix)
[(2, 1), (2, 0), (0, 0), (0, 1)]

>>> find_cycle((0, 2), matrix)
[(2, 2), (2, 0), (0, 0), (0, 2)]

>>> find_cycle((0, 3), matrix)
[(2, 3), (2, 0), (0, 0), (0, 3)]

>>> find_cycle((0, 4), matrix)
[(1, 4), (1, 1), (2, 1), (2, 0), (0, 0), (0, 4)]

>>> find_cycle((1, 0), matrix)
[(1, 1), (2, 1), (2, 0), (1, 0)]

>>> find_cycle((1, 2), matrix)
[(2, 2), (2, 1), (1, 1), (1, 2)]

>>> find_cycle((1, 3), matrix)
[(2, 3), (2, 1), (1, 1), (1, 3)]

>>> find_cycle((2, 4), matrix)
[(2, 1), (1, 1), (1, 4), (2, 4)]

UPD: мое решение выглядит так, полагаю, что я неправильно сделал условия добавления вершин в общий список (строки с pathloop.append(neighbor_row) и pathloop.append(neighbor_col)).

В моем тексте рассуждения:

  • Фиктивный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке НЕТ другого соседа
  • Нормальный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке ЕСТЬ другой сосед

UPD2: у меня есть две идеи по решению это задачи, но я вообще не понимаю, как их можно реализовать:

  1. Через цикл (но тогда надо правильно написать условие добавления вершин в цикл): фактически мы составляем цикл только по нормальным соседям (Нормальный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке ЕСТЬ другой сосед)., поэтапно проверяя их на нормальность сначала по строке, затем по столбцу. Всех нормальных добавляем в список, всех фиктивных - пропускаем.

  2. Через рекурсию - так как в строке/столбце у нас может быть несколько соседей, то каждого надо проверить на нормальность, что отчасти похоже на рекурсивный алгоритм:

    1. поэтапно (один за другим) проверяем всех соседей в данной строке/столбце на нормальность;
    2. если хотя бы один оказался фиктивным, то все соседи, проверенные до него являются фиктивными и их как вершины нашего цикла мы не добавляем в список вершин. Это может работать так: Для point == (0, 2) вершины (1, 1), (2, 1) и (1, 4) являются фиктивными, так как у них нет нормальных соседей, и мы их не должны добавить в список вершин.
    3. рано или поздно мы найдем нормального соседа, которого и добавим в список вершин
def neighbors(pos: tuple, matrix: list) -> list:
    """
    Вернуть координаты ненулевых фиктивных и нормальных соседей указанной ячейки по строке и столбцу

    Ненулевой сосед - такая ячейка матрицы, которая не равна нулю и самой себе.
    Соседи могут находится по строке и столбцам соответственно

    Фиктивный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке НЕТ другого соседа
    Нормальный сосед - ячейка матрицы по строке/столбцу, рядом с которой на столбце/строке ЕСТЬ другой сосед
    """
    # создаем структуру для хранения соседей
    neighbors = {"row": [], "col": []}
    # записываем позицию, вокруг которой будем искать соседей
    crow, ccol = pos
    
    # ищем соседей по колонке
    for row in range(len(matrix)):
        # если найденное значение ненулевое и его позиция не равна заданной
        if matrix[row][ccol] != 0 and pos != (row, ccol):
            # это наш сосед по столбцу
            neighbors["col"].append((row, ccol))

    # ищем соседей по строке
    for col in range(len(matrix[0])):
        # если найденное значение ненулевое и его позиция не равна заданной
        if matrix[crow][col] != 0 and pos != (crow, col):
            # это наш сосед по строке
            neighbors["row"].append((crow, col))

    # возвращаем словарь соседей
    return neighbors


def find_cycle(matrix: list, point: tuple):
    """
    m: чистая матрица
    point: координаты ПУСТОЙ точки, с которой должен начинаться цикл

    :return: list
    """
    # копируем матрицу, чтобы не изменять глобальный объект
    m_copy = matrix
    # записываем строку столбец переданной позиции
    row, column = point
    # по переданной позиции в копии матрицы начальную клетку делаем -1
    m_copy[row][column] = -1
    
    # список вершин
    pathloop = []

    # сохраняем координаты точки
    local_point = point

    # пока искомая точка не находится в списке вершин
    while point not in pathloop:
        
        # ищем ненулевых соседей по строке
        neighbors_by_row =  neighbors(local_point, m_copy)["row"]

        # для каждого из них...
        for i, neighbor_row in enumerate(neighbors_by_row):
            # ...найдем соответствующего соседа по столбцу
            neighbors_by_col = neighbors(neighbor_row, m_copy)["col"]
            
            # если мы нашли такого ненулевого соседа по столбцу
            if neighbors_by_col:
                # то для первого попавшегося из них...
                # как я понимаю - ошибка где то тут, в условии сохранения соседей как вершин
                for j, neighbor_col in enumerate(neighbors_by_col):
                    # сохраним найденного соседа по строке как вершину цикла
                    pathloop.append(neighbor_row)

                    # сохраним найденного соседа по столбцу как вершину цикла
                    pathloop.append(neighbor_col)
                    
                    # найденного соседа по столбцу сохраним как точку
                    # для которой по строке мы также будем искать ненулевого соседа
                    local_point = neighbor_col

                    # выходим, так как нам нужен первый попавшийся сосед
                    break

    # возвращаем список вершин
    return pathloop

matrix = [
    [50, 0, 0, 0, 0],
    [0, 60, 0, 0, 40],
    [50, 10, 50, 40, 0]
]

# должен вывести: [(2, 2), (2, 0), (0, 0), (0, 2)]
# выводит: [(0, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2)]
# то есть в списке есть лишние точки: (2, 1), (1, 1)
# через которые цикл не должен проходить
print(find_cycle(matrix, (0, 2)))
python массивы алгоритм оптимизация рекурсия
Источник: Stack Overflow на русском

Ответы

▲ 0Принят

Логически - задачу надо решать рекурсивным обходом допустим путей в глубину. Чтоб вернуться к исходной вершине надо, чтоб она попала в список соседей, для этого временно делаем ей ненулевое значение -1. Выбираем первоначальное движение - допустим по строке, затем по столбцу и т. д. пока в списке соседей не появиться стартовая вершина.

matrix = [
    [50, 0, 0, 0, 0],
    [0, 60, 0, 0, 40],
    [50, 10, 50, 40, 0]
]
start_points = [(0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 2), (1, 3), (2, 4)]


FLAG_END = False


def find_cycle(mat: list, pos: tuple, dir_row: bool = True, path: list = None) -> list:
    """ Построение цикла опорного плана транспортной задачи.
        При условии, что цикл существует и он единственный.
    """
    global FLAG_END

    if not path:
        path = [pos]
    ii, jj = pos
    # Собираем сначала соседей по строке, потом через раз на повороте.
    if dir_row:
        neighbors = [(ii, k) for k in range(len(mat[0])) if k != jj and mat[ii][k]]
    # Собираем соседей по столбцу на каждом втором повороте.
    else:
        neighbors = [(k, jj) for k in range(len(mat)) if k != ii and mat[k][jj]]
    # Если есть соседи:
    if neighbors:
        # Если стартовая точка есть в списке соседей - путь найден!
        if start_point in neighbors:
            FLAG_END = True
            return path
        else:
            # Меняем направление для поворота.
            dir_row = not dir_row
            # Перебираем всех соседей.
            for neighbor in neighbors:
                # Кладем очередную вершину в список пути.
                path.append(neighbor)
                # Запускаем рекурсию по ненулевым соседям.
                find_cycle(mat, neighbor, dir_row, path)
                # Если нашли путь дальше не перебираем.
                if FLAG_END:
                    break
                # Если путь не найден, то удаляем вершину из списка пути.
                else:
                    path.pop()
    return path

for start_point in start_points:
    i, j = start_point
    matrix[i][j] = -1
    way = find_cycle(matrix, start_point)
    matrix[i][j] = 0
    FLAG_END = False
    print(way)

--------------------------------------

 [(0, 1), (0, 0), (2, 0), (2, 1)]
[(0, 2), (0, 0), (2, 0), (2, 2)]
[(0, 3), (0, 0), (2, 0), (2, 3)]
[(0, 4), (0, 0), (2, 0), (2, 1), (1, 1), (1, 4)]
[(1, 0), (1, 1), (2, 1), (2, 0)]
[(1, 2), (1, 1), (2, 1), (2, 2)]
[(1, 3), (1, 1), (2, 1), (2, 3)]
[(2, 4), (2, 1), (1, 1), (1, 4)]

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