Compartilhamento de tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Índice

Algoritmo Floyd

definição

Uso

Precauções

Ideias para resolução de problemas

Os passos básicos

AcWing 343. Classificação

Descrição da pergunta

executar código

Ideias de código

Melhorar ideias

Algoritmo Floyd

definição

O algoritmo de Floyd, nome completo do algoritmo Floyd-Warshall, é um algoritmo de programação dinâmica usado para resolver o problema do caminho mais curto entre todos os pares de vértices no gráfico. É adequado para gráficos direcionados ponderados e pode lidar com arestas de peso negativo (mas não gráficos contendo ciclos de peso negativo) e pode detectar se há ciclos de peso negativo no gráfico.

Uso

1. Calcule o caminho mais curto entre todos os pares de vértices: Em áreas como análise de redes sociais, planejamento de redes de transporte, projeto de redes de comunicação, etc., o algoritmo Floyd é uma boa escolha quando é necessário calcular a distância mais curta entre dois pontos quaisquer.
2. Detecte ciclos de peso negativos: Em alguns cenários de aplicação é necessário garantir que não existam ciclos de pesos negativos no gráfico, pois isso pode indicar alguma anormalidade ou estado de erro no sistema.

Precauções

• consumo de memória : A complexidade espacial do algoritmo de Floyd é O (n ^ 2), onde n é o número de vértices no gráfico. Para gráficos de grande escala, isso pode se tornar um problema.
• complexidade de tempo: A complexidade de tempo do algoritmo de Floyd é O (n ^ 3). Quando o número de vértices é grande, o algoritmo pode se tornar muito lento.
• loop de peso negativo : Se houver um ciclo de peso negativo no gráfico, o algoritmo de Floyd cairá em um loop infinito, pois a partir de um nó, o comprimento do caminho pode ser reduzido infinitamente através deste ciclo. Em aplicações práticas, tais situações precisam ser detectadas e tratadas primeiro.
• Algoritmos podem detectar ciclos de peso negativos:Se durante a execução do algoritmo for constatado que o caminho mais curto de um vértice até ele mesmo é menor que 0, ou seja, D[i][i] < 0, então existe pelo menos um ciclo de peso negativo no grafo, e o algoritmo não pode fornecer o resultado correto do caminho mais curto neste momento.
• Para gráficos muito grandes, a alta complexidade de tempo e espaço do algoritmo pode se tornar um gargalo. Neste momento, pode ser necessário considerar algoritmos mais eficientes ou usar estruturas de dados e técnicas de otimização mais profissionais.

Ideias para resolução de problemas

A ideia central do algoritmo do Floyd é a programação dinâmica, e suas etapas básicas são as seguintes:

1. Inicialização: Defina a matriz de distância D para a matriz de adjacência do grafo, ou seja, D[i][j] = peso(i, j); para i != j, se (i, j) não estiver conectado, então D[i][ j] = ∞;
2. Programação dinâmica: Para k = 1 a n, atualize D tal que D[i][j] = min(D[i][j], D[i][k] + D[k][j]), que is Verifique se a distância de i a j pode ser encurtada através do nó intermediário k.
3. Resultado: A matriz D final contém os comprimentos de caminho mais curtos entre todos os pares de vértices. Se houver um certo D[i][j] < 0 e i != j, e D[i][i] < 0 ocorrer durante o processo de atualização, significa que há um ciclo de peso negativo no gráfico.

A implementação do algoritmo de Floyd geralmente usa um loop triplo. O loop externo percorre todos os vértices intermediários k e os dois loops internos percorrem todos os pares de vértices (i, j) para verificar se existe um caminho mais curto.

Os passos básicos

Suponha que temos um gráfico ponderado G contendo n vértices, podemos usar uma matriz bidimensionaldist[][] para armazenar o menor comprimento do caminho entre cada par de vértices. Inicialmente,dist[i][j]é definido como o peso da aresta diretamente conectada no gráfico. Se não houver nenhuma aresta diretamente conectada entre i e j, então.dist[i][j]Definido como infinito (indicando inacessível).

1. inicialização : Crie uma matriz n×n D, onde D[i][j] é inicializado com o peso da aresta direta de i a j no gráfico ou definido como infinito se não houver aresta direta entre i e j. Elemento diagonal D[i][i] = 0.

2. programaçao dinamica : Para cada vértice k (como vértice intermediário), atualize o caminho mais curto entre cada par de vértices i e j. É possível obter um caminho mais curto com k como ponto intermediário. A fórmula de atualização é: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Isso significa que se o caminho de i para j se tornar mais curto via k como um vértice intermediário, atualize D[i][j].

3. Saída de resultado: Após n rodadas de iterações, cada elemento D[i][j] na matriz D tem o comprimento de caminho mais curto de i a j.

AcWing 343. Classificação

Descrição da pergunta

343. Classificação - Banco de Perguntas AcWing

executar código

#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
#define PII pair<int, int>
#define fi first
#define se second
#define endl 'n'
map<int, int> mp;
 
const int N = 210, mod = 1e9 + 7;
int T, n, m, k;
int a[N], dist[N][N];
PII ans[N];
 
void floyd(int x) // 以 x 为中转点，更新其他点。
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
}
 
bool pd() // 判断是否所有点都已确定
{
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++)
            if (dist[i][j] != 1e9)
                cnt++; // 当前点能到达的点数
        ans[i] = {cnt, i};
        for (int j = 1; j <= n; j++)
            if (i != j && dist[j][i] != 1e9)
                cnt++; // 能到达当前点的点数
        if (cnt != n)
            return 0;
    }
    sort(ans + 1, ans + n + 1);
    return 1;
}
 
int main() {
    while (cin >> n >> m && n) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)
                    dist[i][j] = 1e9;
 
        int flag = 0;
        for (int i = 1; i <= m; i++) {
            char a, t, b;
            cin >> a >> t >> b;
            int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
 
            if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y，出现矛盾
            {
                printf("Inconsistency found after %d relations.n", i);
                flag = 1;
            }
 
            dist[y][x] = 1;
            floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
            if (!flag && pd()) { // 发现所有点都已确定
                printf("Sorted sequence determined after %d relations: ", i);
                for (int i = 1; i <= n; i++)
                    cout << char(ans[i].se + 'A' - 1);
                printf(".n");
                flag = 1;
            }
        }
        if (!flag)
            printf("Sorted sequence cannot be determined.n"); // 无法确定
    }
 
    return 0;
}

Ideias de código

1. inicialização: use umdistA matriz bidimensional é inicializada até o infinito, o que significa que não há uma relação de ordem definida entre as desigualdades por padrão.
2. Ler entrada: Leia o relacionamento da entrada padrão no formato "B > A", indicando que B é melhor que A.
3. Processamento de relacionamento:
   • Quando uma nova relação é lida, verifica-se se há alguma contradição (ou seja, uma relação previamente determinada entra em conflito com a nova relação).
   • renovardistMatrix, usando o algoritmo de Floyd para atualizar o caminho mais curto entre todas as desigualdades, aqui está na verdade atualizando a relação de “prioridade” ou “ordenação”.
4. Verifique a certeza da classificação:
   • Verifique se todas as desigualdades estão relacionadas, ou seja, cada ponto pode alcançar todos os outros pontos e o comprimento do caminho não é infinito.
   • Se a classificação for encontrada durante o processo de leitura do relacionamento, ou se a classificação ainda não puder ser determinada após a leitura de todos os relacionamentos, as informações correspondentes serão geradas.

Melhorar ideias

• Melhoria de eficiência : a chamada atual do Floyd é feita imediatamente após cada novo relacionamento ser adicionado, o que pode não ser necessário. Você pode esperar até que todas as relações tenham sido lidas antes de executar novamente o algoritmo do Floyd para reduzir cálculos desnecessários.
• Simplifique a lógica : O código atual é mais complexo na detecção de contradições e na determinação da lógica de conclusão da classificação. Você pode tentar simplificar a lógica, como usar estruturas de dados mais intuitivas ou etapas algorítmicas para verificar essas condições.
• clareza de código: pode aumentar a clareza dos comentários e da estrutura do código, tornando o código mais fácil de entender e manter.