如何将此递归函数转换为迭代函数？

绝地武士山姆

我无法将此方法从递归转换为迭代。我具体遇到的问题是我不知道如何转换作为if语句条件的递归调用。

这样做是因为我使用的数据集导致堆栈溢出异常。

必须有一堆索引，这些索引当前是用于递归调用的参数，但是除此之外，我不知道该怎么办。

    public static IEnumerable<BipartiteMatch> MaximumBipartiteMatch(int m, int n, Func<int, int, bool> isMapped)
    {
        var matches = new int[n];

        for (var i = 0; i < n; ++i)
        {
            matches[i] = -1;
        }

        for (var x = 0; x < m; x++)
        {
            BipartiteMatch(x, n, new bool[n], matches, isMapped);
        }

        for (var index = 0; index < n; index++)
        {
            yield return new BipartiteMatch(matches[index], index);
        }
    }

    private static bool BipartiteMatch(int x, int n, bool[] seen, int[] matches, Func<int, int, bool> isMapped)
    {
        for (var y = 0; y < n; y++)
        {
            if (seen[y] || !isMapped(x, y)) continue;

            seen[y] = true;

            //HERE:
            if (matches[y] >= 0 && !BipartiteMatch(matches[y], n, seen, matches, isMapped)) continue;

            matches[y] = x;
            return true;
        }

        return false;
    }

如果为matches[y] >= 0，则需要将的值压入matches[y]堆栈，但是我不确定如何循环它以模拟递归。

我的尝试（越野车）：

internal static class MaximumMatchingAlgorithm
{
    internal static IEnumerable<BipartiteMatch> Solve(int m, int n, Func<int, int, bool> isMapped)
    {
        const int invalid = -1;

        var mappings = new Stack<int>[m];
        var matches = new int[n];

        for (var index = 0; index < n; index++)
        {
            matches[index] = invalid;
        }

        for (var x = 0; x < m; x++)
        {
            var mapping = mappings[x] = new Stack<int>(n);

            for (var y = 0; y < n; y++)
            {
                if (isMapped(x, y))
                {
                    mapping.Push(y);
                }
            }

            var currentX = x;

            while (mapping.TryPop(out var y))
            {
                var tempX = matches[y];
                var otherMapping = tempX != invalid ? mappings[tempX] : null;

                if (otherMapping == null)
                {
                    matches[y] = currentX;
                    break;
                }

                if (otherMapping.Count == 0) continue;

                matches[y] = currentX;
                currentX = tempX;
                mapping = otherMapping;
            }
        }

        for (var index = 0; index < n; index++)
        {
            yield return new BipartiteMatch(matches[index], index);
        }
    }
}

更新：

这是继@EricLippert评论后的第二次尝试。我创建了一个State值来存储循环在哪里停止，以便它可以模拟递归过程中发生的暂停。某个地方仍然存在错误，但是我认为这可能会越来越近。

    public struct State
    {
        public int X { get; set; }

        public int Y { get; set; }

        public bool Result { get; set; }
    }

    public static void BipartiteMatch(int x, int n, bool[] seen, int[] matches, Func<int, int, bool> isMapped)
    {
        var stack = new Stack<State>();
        stack.Push(new State {X = x, Y = -1});

        while (stack.TryPop(out var state))
        {
            if (state.Y != -1 && state.Result)
            {
                matches[state.Y] = state.X;
            }
            else
            {
                for (var y = state.Y != -1 ? state.Y : 0; y < n; y++)
                {
                    if (seen[y] || !isMapped(state.X, y)) continue;

                    seen[y] = true;

                    if (matches[y] >= 0)
                    {
                        stack.Push(new State {X = state.X, Y = y});
                        stack.Push(new State {X = matches[y], Y = -1});
                        break;
                    }

                    if (stack.TryPop(out state))
                    {
                        stack.Push(new State {X = state.X, Y = state.Y, Result = true});
                        break;
                    }

                    matches[y] = state.X;
                    return;
                }
            }
        }
    }

绝地武士山姆

我想我可能已经弄明白了，但是在我说这一切都很好之前，我想再说一遍。

这里的逻辑是每次将使用递归时，将循环的当前状态与可以回答先前堆叠状态是否有效的状态一起推入堆栈。如果问题的答案是正确的，则将整个堆栈解开，并且该方法终止，否则，继续搜索。

    public readonly struct State
    {
        public State(int x, int y = 0)
        {
            X = x;
            Y = y;
        }

        public int X { get; }

        public int Y { get; }
    }

    public static void BipartiteMatch(int x, int n, bool[] seen, int[] matches, Func<int, int, bool> isMapped)
    {
        var stack = new Stack<State>(new[] {new State(x)});

        while (stack.TryPop(out var state))
        {
            for (var y = state.Y; y < n; y++)
            {
                if (seen[y] || !isMapped(state.X, y)) continue;

                seen[y] = true;

                if (matches[y] >= 0)
                {
                    stack.Push(new State(state.X, y));
                    stack.Push(new State(matches[y]));
                    break;
                }

                matches[y] = state.X;

                while (stack.TryPop(out state))
                {
                    matches[state.Y] = state.X;
                }

                break;
            }
        }
    }

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。