Noble Badass Ответов: 4

Программа для поиска минимальной матрицы

Minimum matrix

You are given an integer matrix A of size N×M. You start on the left upper corner cell (with coordinates (1,1)). You can walk in four directions. You can not visit the same cell twice. You have to visit every cell of matrix A. When you stand on a cell, your maximum value is updated with the value of element on this cell. Initially, the maximum value is equal to A1,1. Your task is to find the path with the minimum number of changes in the maximum value.

SAMPLE INPUT 
3 3
2 1 7
4 1 6
7 4 8

SAMPLE OUTPUT 
1 1
1 2
1 3
2 3
3 3
3 2
2 2
2 1
3 1


Что я уже пробовал:

Maximum value initially is equal to 2 and you stood on cell (1, 1). Then you walked on element 1, maximum did not updated. After that you went on element 7, maximum value has become 7. Then you walked on element 6, nothing changed. After that you went on element 8, maximum value has become 8.

Stefan_Lang

Подсказки:
0. раздел "Быстрые ответы" предназначен для того, чтобы помочь людям исправить проблемы с синтаксисом языка, заставить программу работать или помочь людям обнаружить ошибку в программе, которая уже работает, но дает неправильные результаты. Где ваша программа?
1. Вы должны публиковать те разделы вашей программы, с которыми у вас возникли проблемы.
2. раздел "Что я пробовал" должен содержать варианты той программы, которую вы пробовали, чтобы получить правильные результаты.

4 Ответов

Рейтинг:
2

OriginalGriff

Мы более чем готовы помочь тем, кто застрял, но это не значит, что мы здесь, чтобы сделать все это для вас! Мы не можем сделать всю работу, вам либо платят за это, либо это часть ваших оценок, и было бы совсем несправедливо, если бы мы сделали все это за вас.

Поэтому нам нужно, чтобы вы сделали работу, и мы поможем вам, когда вы застряли. Это не значит, что мы дадим вам пошаговое решение, которое вы можете сдать!
Начните с объяснения, где вы находитесь в данный момент и каков следующий шаг в этом процессе. Затем расскажите нам, что вы пытались сделать, чтобы этот следующий шаг сработал, и что произошло, когда вы это сделали.

Рейтинг:
2

Maciej Los

Взгляните сюда: Алгоритм дейсктры[^]

Stefan_Lang

Это вариант задачи коммивояжера с очень специальной функцией затрат. К сожалению, это еще хуже, потому что для оценки функции стоимости вам нужно знать полный путь - поэтому вы не можете использовать алгоритм Дейкстры.

Maciej Los

Well, i must admit that i disagree. A TSP is used when you have a list of cities and different distances between each pair of cities (cells). In this case the distance between each cell is the same (1 step in any direction). In TSP you have to find the shortest route to the next city and finally return to the initial city. By using Dijkstra’s algorithm you're trying to find the shortest path from source to all vertices in the given graph. The graph is well known, because it is a set of cells in defined area (3x3). All what OP have to do is to find the shortest path to the cell with maximum value. The most important thing is that, that initial position in a graph has been provided - it's a cell (1,1) and the first move can be make in one of directions: right or down.
Овации
Мацей

Stefan_Lang

Алгоритм Дейкстры здесь не работает: он не заботится о посещении всех городов, и он требует способности оценить частичный путь таким образом, чтобы он был значимым для решения, как построить полный путь. К сожалению, оценка требует знания полного пути, так что это невозможно сделать!

TSP ближе к этой проблеме в том, что вы должны посетить все ячейки, ровно один раз. То, что вам не нужно возвращаться к началу, - это всего лишь незначительная вариация. График, который у вас есть, представляет собой простую сетку с соединениями с (до) четырьмя соседними ячейками, и стоимость перемещения по определенному пути может быть оценена, как только вы построите правильный путь.

Сказав это, если вы можете представить работающий алгоритм, основанный на Дейкстре, то вы доказали, что либо это не проблема TSP, либо что P=NP! Я сомневаюсь, что вы можете, но я был бы счастлив, если бы оказалось, что вы ошибаетесь. :-)

Maciej Los

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

Рейтинг:
0

Stefan_Lang

Это один из вариантов задача коммивояжера[^] (вы должны посетить все ячейки матрицы) с необычной функцией стоимости. Функция затрат может быть оценена только после того, как у вас есть полный путь. Кроме того, полный путь должен посетить все ячейки. Вы migth хотите посмотреть реализации этого Шаблон Посетителя[^] чтобы получить представление о том, как может выглядеть код.

Для решения задачи необходимо перечислить все пути через матрицу. Поскольку у вас есть не более 4 направлений для перехода из каждой ячейки, а длина пути должна быть NxM, общее количество путей, начинающихся в ячейке (1,1), меньше 4^(N*M-1) (4 в степени (N*M-1), но это все равно много. Вероятно, лучше избегать тех путей, которые не могут быть решением, например, отслеживая, какие ячейки вы уже посетили, и не выбирая направление к ячейке, которую вы уже посетили.

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

struct node {
    // links to neighbouring cells of the matrix (may be nullptr):
    node* up;
    node* down;
    node* left;
    node* right;
    // position of the cell within the matrix
    int row;
    int column;
    // next node of the current path
    node* next;
};
struct matrix {
    node* first;
};

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

В общем, это большой код для написания, но если вы будете следовать приведенному выше наброску, это не должно быть слишком сложно.

Рейтинг:
0

Patrice T

Цитата:
Программа для поиска минимальной матрицы

Да, это то, что вы должны сделать !
На этом сайте мы помогаем вам исправить вашу программу, но вам нужна программа, Мы не делаем за вас домашнюю работу.
Это требование типично для сложных сайтов, поэтому ваша задача-решить проблему, в вашем случае вы потерпели неудачу.
Неудача в решении проблемы с вашей собственной работой лучше, чем успех с чьей-то другой работой.

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

Stefan_Lang

- Насколько я понимаю, грубая сила-это единственный выход. "
Да, это вариант задачи коммивояжера с очень специальной функцией затрат. К сожалению, это еще хуже, потому что для оценки функции стоимости вам нужно знать полный путь - поэтому вы не можете использовать алгоритм Дейкстры.